#include <iostream>
#include <map>
#include <list>
#include <vector>
#include <set>
#include <cmath>
#include <memory>
#include <ctime>

using namespace std;

static const int MAPLEN = 10;
static const int MAPWID = 10;
static const int RANGE = 2;
static const int TICKLEN = 2;

struct Pos
{
    int x_, y_;
};

struct Location
{
    int x_, y_, dx_, dy_;
};

struct SItComp
{
    bool operator()(const map<int64_t, Location>::iterator &lhs, const map<int64_t, Location>::iterator &rhs)
    {
        return lhs->first < rhs->first;
    }
};

struct Ret
{
    int x_, y_, dx_, dy_;
    int64_t uid;
};
ostream &operator<<(ostream &out, const Ret &r)
{
    out << "{x:" << r.x_ << ",y:" << r.y_ << ",dx:" << r.dx_ << ",dy:" << r.dy_ << ",uid:" << r.uid << "}";
    return out;
}

struct Aoi
{
    set<int64_t> players_;
    map<int64_t, Location> entities_;
    vector<vector<set<map<int64_t, Location>::iterator, SItComp>>> grids_;

    Aoi()
        : grids_((MAPLEN - 1) / RANGE + 1, vector<set<map<int64_t, Location>::iterator, SItComp>>((MAPWID - 1) / RANGE + 1))
    {
    }

    void addPlayer(const int64_t &id, const Location &l);
    void delPlayer(const int64_t &id);
    void addEntity(const int64_t &id, const Location &l);
    void delEntity(const int64_t &id);
    void changeDir(const int64_t &id, const int dx, const int dy);

    static bool locSideCheck(const Location &l);

    void oneMove(const int64_t &id);
    void allMove();
    void addGridDataToRet(int gx, int gy, vector<Ret> &ret);
    void getOneAoi(const int64_t &id, vector<Ret> &ret);
    void getAoi(map<int64_t, vector<Ret>> &ret);
};

bool Aoi::locSideCheck(const Location &l)
{
    if (l.x_ < 0 || l.x_ >= MAPLEN || l.y_ < 0 || l.y_ >= MAPWID)
        return false;
    return true;
}

void Aoi::addPlayer(const int64_t &id, const Location &l)
{
    if (!locSideCheck(l))
        return;
    if (players_.end() != players_.find(id))
        return;
    players_.insert(id);
    addEntity(id, l);
}

void Aoi::delPlayer(const int64_t &id)
{
    if (players_.end() == players_.find(id))
        return;
    players_.erase(id);
    delEntity(id);
}

void Aoi::addEntity(const int64_t &id, const Location &l)
{
    if (!locSideCheck(l))
        return;
    if (entities_.end() != entities_.find(id))
        return;
    auto it = entities_.insert(make_pair(id, l));
    int gx = l.x_ / RANGE;
    int gy = l.y_ / RANGE;
    grids_[gx][gy].insert(it.first);
}

void Aoi::delEntity(const int64_t &id)
{
    auto it = entities_.find(id);
    if (entities_.end() == it)
        return;
    int gx = it->second.x_ / RANGE;
    int gy = it->second.y_ / RANGE;
    grids_[gx][gy].erase(it);
    entities_.erase(id);
}

void Aoi::changeDir(const int64_t &id, const int dx, const int dy)
{
    if (entities_.end() == entities_.find(id))
        return;
    auto &lo = entities_[id];
    lo.dx_ = dx;
    lo.dy_ = dy;
}

void Aoi::oneMove(const int64_t &id)
{
    auto &lo = entities_[id];
    if (!lo.dx_ && !lo.dy_)
        return;
    int idx = TICKLEN / sqrt(pow(lo.dx_, 2) + pow(lo.dy_, 2));
    Location l{lo.x_ + idx * lo.dx_, lo.y_ + idx * lo.dy_, lo.dx_, lo.dy_};
    if (l.x_ < 0)
        l.x_ = 0;
    if (l.x_ >= MAPLEN)
        l.x_ = MAPLEN - 1;
    if (l.y_ < 0)
        l.y_ = 0;
    if (l.y_ >= MAPWID)
        l.y_ = MAPWID - 1;
    if (lo.x_ / RANGE == l.x_ / RANGE && lo.y_ / RANGE == l.y_ / RANGE)
    {
        lo.x_ = l.x_;
        lo.y_ = l.y_;
        return;
    }
    else
    {
        delEntity(id);
        addEntity(id, l);
    }
}

void Aoi::allMove()
{
    for (auto &it : entities_)
    {
        oneMove(it.first);
    }
}

void Aoi::addGridDataToRet(int gx, int gy, vector<Ret> &ret)
{
    if (gx < 0 || gx >= grids_.size())
        return;
    if (gy < 0 || gy >= grids_[gx].size())
        return;
    for (const auto &it : grids_[gx][gy])
    {
        const int64_t &ido = it->first;
        const auto &loc = it->second;
        ret.push_back({loc.x_, loc.y_, loc.dx_, loc.dx_, ido});
    }
}

void Aoi::getOneAoi(const int64_t &id, vector<Ret> &ret)
{
    const auto &lo = entities_[id];
    const int gx = lo.x_ / RANGE;
    const int gy = lo.y_ / RANGE;

    static vector<Pos> directs = {
        {-1, 1}, {0, 1}, {1, 1}, {-1, 0}, {0, 0}, {1, 0}, {-1, -1}, {0, -1}, {1, -1}};
    for (const auto &d : directs)
    {
        int gx1 = gx + d.x_;
        int gy1 = gy + d.y_;
        addGridDataToRet(gx1, gy1, ret);
    }
}

void Aoi::getAoi(map<int64_t, vector<Ret>> &ret)
{
    for (const auto &id : players_)
    {
        getOneAoi(id, ret[id]);
    }
}

int main()
{
    auto p = make_unique<Aoi>();
    for (int i = 0; i < MAPLEN; ++i)
    {
        p->addPlayer(i, {i, i, 1, 1});
    }

    p->allMove();
    map<int64_t, vector<Ret>> ret;
    p->getAoi(ret);

    for (const auto &it : ret)
    {
        cout << it.first << ":";
        for (const auto &itt : it.second)
        {
            cout << itt;
        }
        cout << endl;
    }
}